package package1;

public class pack {

	public static void main(String[] args) {
		int m=10;  // 总容量
		int n=3; // 物品个数
		int w[]= {5,4,3}; // 物品的体积
		int v[]= {6,5,4}; // 物品价值
		int [][] k=new int [n+1][m+1];  // 动态规划的二维数组
		k=test(m,n,w,v);
		for(int i=0;i<=n;i++)
			for(int j=0;j<=m;j++) {
				System.out.print("  "+k[i][j]);
				if(j==m)
					System.out.println();
			}
		System.out.println("test00:"+test00(m,n,w,v));

	}
	/** 
	 * 动态规划算法
	 * @param m 总容量
	 * @param n 物品个数
	 * @param w 物品体积数组
	 * @param v 物品价值数组
	 * @return 动态规划的结果数组
	 */
	private static int [][] test(int m,int n, int[] w,int[] v){
		// 动态规划数组，为了方便动态规划条件从1开始，数组维数+1
		int [][] c=new int[n+1][m+1];
		// 初始化
		for(int i=1;i<n+1;i++)
			for(int j=1;j<m+1;j++) {
				c[i][j]=0;
			}
		// 填充动态规划数组
		// 变量物品个数，尝试每个物品进行规划处理
		for(int i=1;i<n+1;i++)
			// 背包容量的遍历规划
			for(int j=1;j<m+1;j++) {
				
				/*
				 * i 表示当前的要动态规划物品 ，该物品还没有放入背包，准备放入背包，i下标从1开始
				 * w数组是物品的体积数组
				 * 因为当前的物品下标从1开始，取出该物品的体积是下标需要-1
				 * 所有 w[i-1] 就是物品i的体积
				 * 
				 * 
				 * c是动态规划的数组，i下标表示当前动态规划处理到了第几个物品；i还没有放入背包中；
				 * j表示当前动态规划到第i个物品时背包的剩余的容量
				 * c[i][j] 数组的值表示当前背包中存放物品i时剩余容量为j是的背包总价值
				 * 
				 * 动态规划条件：
				 * 分为两种情况进行处理：
				 * 1、当前物品i无法放入背包：
				 * 当前物品i不放入背包，条件是剩余容量j小于当前物品i的容量w[i-1] 【数组值  w[i-1] 表示物品i的容量 】
				 * 2、当前物品i可以放入背包：
				 * 当前物品i可以放入背包，条件是剩余容量j大于等于当前物品i的容量w[i-1]，
				 * 此时处理有两种选择，一种是放入物品i：
				 *    此时背包中放入物品i之后，则背包剩余容量为j-w[i-1]，c[i-1][j-w[i-1]]是此时背包剩余容量为j-w[i-1]的最优解，
				 *    即放入物品i之后背包总价值为c[i-1][j-w[i-1]]+v[i-1]；
				 * 还有一种选择就是不放入物品i，选择放入物品i之前的其他物品，此时的背包价值为 c[i-1][j]
				 * 
				 * 这也是为什么使用max函数的原因；
				 * 
				 * c[i-1][j]表示放入物品i之前的背包的价值；
				 * w[i-1] 表示物品i的容量；
				 * c[i-1][j-w[i-1]] 在物品i放入之后，背包剩余容量为j-w[i-1]时的最优解(这个最优解是在上轮循环时计算得出的)；
				 * 				           （此时，背包中已经装入物品i，但是还有剩余容量； ）  
				 * 
				 * c[i-1][j-w[i-1]]+v[i-1] 值表示背包中放入物品i之后，背包的容量为j时的价值； 
				 * 
				 */
				if(w[i-1]>j) {
					c[i][j] =c[i-1][j];
				}
				else {
					c[i][j]=Math.max(c[i-1][j],c[i-1][j-w[i-1]]+v[i-1]);
				}
				
				//当背包里的物品为i件重量为j时，如果第i件的重量为weight【i-1】小于重量j时，c【i】【j】有下列两种情况
				//(1)物品i不放入背包，所以dp[i][j]为dp[i-1][j]的值
				//(2)物品i放入背包，则背包剩余重量为j-weight[i-1]，所以从dp[i][j]为dp[i-1][j-weight[i-1]]的值加上当前物品i的值				

			
			}		
		return c;
	}
	/** 
	 * 动态规划算法
	 * @param m 总容量
	 * @param n 物品个数
	 * @param w 物品体积数组
	 * @param v 物品价值数组
	 * @return 动态规划的结果数组
	 */
	private static int test00(int m,int n, int[] w,int[] v){
		int[] c=new int[m+1];
		// 下标i表示 第几个物品， w[i-1]表示物品i的体积
		for(int i=1;i<n+1;i++) {
			/*
			 * j 表示背包的剩余容量
			 * 
			 * 循环条件是 背包剩余容量还可以继续放入物品
			 * 
			 */
			for(int j=m;j>=w[i-1];j--) {
				
					c[j]=Math.max(c[j],c[j-w[i-1]]+v[i-1]);
			}
		}
		return c[m];

	}

}
